Search for: All records

Robust optimization (RO) is a popular paradigm for modeling and solving two- and multistage decision-making problems affected by uncertainty. In many real-world applications, such as R&D project selection, production planning, or preference elicitation for product or policy recommendations, the time of information discovery is decision-dependent and the uncertain parameters only become observable after an often costly investment. Yet, most of the literature on robust optimization assumes that the uncertain parameters can be observed for free and that the sequence in which they are revealed is independent of the decision-maker’s actions. To fill this gap in the practicability of RO, we consider two- and multistage robust optimization problems in which part of the decision variables control the time of information discovery. Thus, information available at any given time is decision-dependent and can be discovered (at least in part) by making strategic exploratory investments in previous stages. We propose a novel dynamic formulation of the problem and prove its correctness. We leverage our model to provide a solution method inspired from the K-adaptability approximation, whereby K candidate strategies for each decision stage are chosen here-and-now and, at the beginning of each period, the best of these strategies is selected after the uncertain parameters that were chosen to be observed are revealed. We reformulate the problem as a finite mixed-integer (resp. bilinear) program if none (resp. some) of the decision variables are real-valued. This finite program is solvable with off-the-shelf solvers. We generalize our approach to the minimization of piecewise linear convex functions. We demonstrate the effectiveness of our method in terms of usability, optimality, and speed on synthetic instances of the Pandora box problem, the preference elicitation problem with real-valued recommendations, the best box problem, and the R&D project portfolio optimization problem. Finally, we evaluate it on an instance of the active preference elicitation problem used to recommend kidney allocation policies to policy-makers at the United Network for Organ Sharing based on real data from the U.S. Kidney Allocation System. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported primarily by the Operations Engineering Program of the National Science Foundation under NSF Award No. 1763108. The authors are grateful for this support. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2021.00160 . 

Human development is a threat to biodiversity and conservation organizations (COs) are purchasing land to protect areas for biodiversity preservation. COs have limited budgets and cannot purchase all the land necessary to perfectly preserve biodiversity, and human activities are uncertain, so exact developments are unpredictable. We propose a multistage, robust optimization problem with a data-driven hierarchical-structured uncertainty set which captures the endogenous nature of the binary (0-1) human land use uncertain parameters to help COs choose land parcels to purchase to minimize the worst-case human impact on biodiversity. In the proposed approach, the problem is formulated as a game between COs, which choose parcels to protect with limited budgets, and the human development, which will maximize the loss to the unprotected parcels. We leverage the cellular automata model to simulate the development based on climate data, land characteristics, and human land use data. We use the simulation to build data-driven uncertainty sets. We demonstrate that an equivalent formulation of the problem can be obtained that presents exogenous uncertainty only and where uncertain parameters only appear in the objective. We leverage this reformulation to propose a conservative $$K$$-adaptability reformulation of our problem that can be solved routinely by off-the-shelf solvers like Gurobi or CPLEX. The numerical results based on real data show that the proposed method reduces conservation loss by 19.46% on average compared to standard approaches used in practice for biodiversity conservation. 

We consider the parameter estimation problem of a probabilistic generative model prescribed using a natural exponential family of distributions. For this problem, the typical maximum likelihood estimator usually overfits under limited training sample size, is sensitive to noise and may perform poorly on downstream predictive tasks. To mitigate these issues, we propose a distributionally robust maximum likelihood estimator that minimizes the worst-case expected log-loss uniformly over a parametric Kullback-Leibler ball around a parametric nominal distribution. Leveraging the analytical expression of the Kullback-Leibler divergence between two distributions in the same natural exponential family, we show that the min-max estimation problem is tractable in a broad setting, including the robust training of generalized linear models. Our novel robust estimator also enjoys statistical consistency and delivers promising empirical results in both regression and classification tasks.